package structures.graph;

import java.util.*;

public class GraphDemo {
    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addVertex("1");
        graph.addVertex("2");
        graph.addVertex("3");
        graph.addVertex("4");
        graph.addVertex("5");
        graph.addVertex("6");
        graph.addVertex("7");
        graph.addVertex("8");
        graph.setEdge("1", "2", 5);
        graph.setEdge("1", "3", 5);
        graph.setEdge("2", "4", 1);
        graph.setEdge("2", "5", 1);
        graph.setEdge("4", "8", 1);
        graph.setEdge("5", "8", 1);
        graph.setEdge("3", "6", 1);
        graph.setEdge("3", "7", 1);
        graph.setEdge("6", "7", 1);

        System.out.println("edge的数量 " + graph.getNumOfEdges());

        graph.showGraph();
        System.out.println("-------------");
//        graph.dfsGraph("2");
        graph.bfsGraph("2");
    }
}

class Graph {
    // 边的总数量
    private int numOfEdges;
    // 顶点的名称
    private final List<String> vertexList;
    // 边的weight
    private final int[][] edges;

    /**
     * 输入vertex(顶点)的数量
     *
     * @param num num
     */
    public Graph(int num) {
        vertexList = new ArrayList<>();
        edges = new int[num][num];
        isVisited = new boolean[num];
        Arrays.fill(isVisited, false);
    }

    /**
     * 添加顶点
     *
     * @param vertex 顶点名称
     */
    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     *
     * @param v1     顶点
     * @param v2     顶点
     * @param weight 权重
     */
    public void setEdge(String v1, String v2, int weight) {
        int v1Index = vertexList.indexOf(v1);
        int v2Index = vertexList.indexOf(v2);
        if (v1Index == -1 || v2Index == -1) {
            return;
        }
        edges[v1Index][v2Index] = weight;
        edges[v2Index][v1Index] = weight;
        numOfEdges++;
    }

    /**
     * 获取顶点的数量
     *
     * @return size
     */
    public int getNumOfVertex() {
        return vertexList.size();
    }

    /**
     * 获取边的数量
     *
     * @return num
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回点到点的权值
     *
     * @param v1 顶点
     * @param v2 顶点
     * @return weight
     */
    public int getWeight(String v1, String v2) {
        int v1Index = vertexList.indexOf(v1);
        int v2Index = vertexList.indexOf(v2);
        if (v1Index == -1 || v2Index == -1) {
            return -1;
        }
        return edges[v1Index][v2Index];
    }

    /**
     * 显示整个graph
     */
    public void showGraph() {
        for (String data : vertexList) {
            System.out.print(data + "\t");
        }
        System.out.println();
        for (int[] edgeX : edges) {
            for (int data : edgeX) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }
    }

    // 存储已经遍历过的数据
    private static boolean[] isVisited;

    /**
     * 深度优先遍历 deep-first-search
     */
    public void dfsGraph(String vertex) {
        int vertexIndex = vertexList.indexOf(vertex);
        if (isVisited[vertexIndex]) {
            return;
        }
        System.out.println(vertex);
        isVisited[vertexIndex] = true;
        for (int i = 0; i < edges[vertexIndex].length; i++) {
            if (edges[vertexIndex][i] != 0) {
                dfsGraph(vertexList.get(i));
            }
        }
    }

    /**
     * 广度优先遍历 breadth-first-search
     *
     * @param vertex 顶点
     */
    public void bfsGraph(String vertex) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add(vertex);
        while (linkedList.size() > 0) {
            String data = linkedList.pollFirst();
            // 获取索引值
            int vertexIndex = vertexList.indexOf(data);
            if (vertexIndex == -1) {
                return;
            }
            // 判断是否已经被探测过
            if (isVisited[vertexIndex]) {
                continue;
            }
            // 输出结果 并标记为探测过
            System.out.println(data);
            isVisited[vertexIndex] = true;
            //  遍历 插入尾端
            for (int index = 0; index < edges[vertexIndex].length; index++) {
                if (edges[vertexIndex][index] != 0) {
                    linkedList.addLast(vertexList.get(index));
                }
            }

        }

    }
}
